package com.wenyl.graph;

import java.util.*;

/**
 * @author Swimming Dragon
 * @description: 图的邻接表存储
 * @date 2024年10月18日 14:04
 */
@SuppressWarnings("unchecked")
public class AdjacencyList {
    private LinkedList<Integer>[] adjList;
    private final int vertices;
    public AdjacencyList(int vertices){
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for(int i=0;i<vertices;i++){
            adjList[i] = new LinkedList<>();
        }
    }
    public void addEdge(int source,int destination){

        int sourceIndex = source - 1;
        int destinationIndex = destination - 1;
        if(!isLegal(sourceIndex,destinationIndex)){
            System.out.println("顶点不存在");
            return;
        }
        // 无向图双边都存在
        adjList[sourceIndex].add(destinationIndex);
        adjList[destinationIndex].add(sourceIndex);
    }
    public void printGraph(){
        for(int i=0;i<vertices;i++){
            System.out.print("顶点"+(i+1)+"的邻接点:   ");
            for (Integer integer : adjList[i]) {
                System.out.print(integer+1 + " ");
            }
            System.out.println();
        }
    }
    public boolean isLegal(int source,int destination){
        return source >=0 && source <vertices && destination >=0 && destination <vertices;
    }

    /**
     * 从指定节点开始做广度优先遍历
     * @param startVertex 起始节点
     */
    public void bfs(int startVertex){
        System.out.println("广度优先遍历结果: ");
        int startVertexIndex = startVertex-1;
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startVertexIndex);
        visited[startVertexIndex] = true;
        while(!queue.isEmpty()){
            int currentVertex = queue.poll();
            System.out.print((currentVertex+1) + " ");
            // 把没有遍历过的并且与这个节点连接的节点放入到队列
            for(Integer edge:adjList[currentVertex]){
                if(!visited[edge]){
                    queue.add(edge);
                    visited[edge] = true;
                }
            }
        }
        System.out.println();
    }

    /**
     * 从指定节点开始做深度优先遍历
     * @param startVertex 起始节点
     */
    public void dfs(int startVertex){
        System.out.println("深度优先遍历结果: ");
        int startVertexIndex = startVertex-1;
        boolean[] visited = new boolean[vertices];
        Stack<Integer> stack = new Stack<>();
        visited[startVertexIndex] = true;
        stack.add(startVertexIndex);
        while(!stack.isEmpty()){
            int currentVertex = stack.pop();
            System.out.print((currentVertex+1) + " ");
            // 把没有遍历过的并且与这个节点连接的节点放入到队列
            for(Integer edge:adjList[currentVertex]){
                if(!visited[edge]){
                    stack.add(edge);
                    visited[edge] = true;
                }
            }
        }
        System.out.println();
    }
}
